package Hot100.Medium.BinaryTree;

import Hot100.Easy.LC104.TreeNode;

import java.util.Stack;

public class LC98_ValidateBST {
    public static void main(String[] args) {

    }

    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;
        // 维护一个前节点，用于比较。
        TreeNode pre = null;
        while(!stack.isEmpty() || curNode != null){
            if (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left; // 先遍历左子树
            } else {
                curNode = stack.pop(); // 处理当前根节点
                // 核心：判断是否严格递增（BST的中序遍历性质）
                if (pre != null && curNode.val <= pre.val) {
                    return false;
                }
                pre = curNode; // 更新前一个节点为当前节点
                curNode = curNode.right; // 遍历右子树
            }
        }
        return true;
    }
}
